#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5, SP = 20;

struct lca
{
    int pa[N][SP], dep[N];
    vector<int> *G;
    void init(vector<int> G[])
    {
        this->G = G;
        dfs(1, 1);
    }
    void dfs(int u, int fa)
    {
        pa[u][0] = fa; dep[u] = dep[fa] + 1;
        for (int i=1; i<SP; ++i)
            pa[u][i] = pa[pa[u][i-1]][i-1];
        for (int v : G[u])
        {
            if (v == fa) continue;
            dfs(v, u);
        }
    }

    int go(int u, int v)
    {
        if (dep[u] < dep[v]) swap(u, v);
        int t = dep[u] - dep[v];
        for (int i=0; i<SP; ++i) if (t & (1 << i)) u = pa[u][i];
        for (int i=SP-1; i>=0; --i)
        {
            int uu = pa[u][i], vv = pa[v][i];
            if (uu != vv) { u == uu; v = vv; };
        }
        return u == v ? u : pa[u][0];
    }
};

namespace treeDiff
{
    int sum[N], a[N];
    
    

}

int main(int argc, char const *argv[])
{
    
    return 0;
}
